package com.jiang.竞赛.周赛.四三二.Q3418;

/**
 * @author Jiang
 * @version 1.0
 * @date 2025/01/13 0:03
 */
class Solution {
    public int maximumAmount(int[][] coins) {
        int row = coins.length;
        int col = coins[0].length;

        int[][][] dp = new int[row][col][3]; // dp[i][j]表示走到 (i,j) 且已经感化 k 次的最大答案

        // 初始化
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                for (int k = 0; k < 3; k++) {
                    dp[i][j][k] = Integer.MIN_VALUE;
                }
            }
        }

        dp[0][0][0] = coins[0][0];
        dp[0][0][1] = 0;
        dp[0][0][2] = 0;

        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                // 不感化
                for (int k = 0; k < 3; k++) {
                    if (i > 0)
                        dp[i][j][k] = Math.max(dp[i][j][k], dp[i - 1][j][k] + coins[i][j]);
                    if (j > 0)
                        dp[i][j][k] = Math.max(dp[i][j][k], dp[i][j - 1][k] + coins[i][j]);
                }

                // 感化
                if (coins[i][j] < 0) {
                    for (int k = 1; k < 3; k++) {
                        if (i > 0)
                            dp[i][j][k] = Math.max(dp[i][j][k], dp[i - 1][j][k - 1]);
                        if (j > 0)
                            dp[i][j][k] = Math.max(dp[i][j][k], dp[i][j - 1][k - 1]);
                    }
                }
            }

        }

        return Math.max(dp[row - 1][col - 1][0], Math.max(dp[row - 1][col - 1][1], dp[row - 1][col - 1][2]));
    }
}
